import java.util.ArrayList;
import java.util.Comparator;
import java.util.PriorityQueue;

/**
 * Created by L.jp
 * Description:合并 k 个升序的链表并将结果作为一个升序的链表返回其头节点。
 * User: 86189
 * Date: 2022-05-12
 * Time: 22:42
 */
//class ListNode {
//      int val;
//      ListNode next;
//      ListNode(int x) {
//          val = x;
//          next = null;
//      }
//}
public class Solution {
    public ListNode mergeKLists(ArrayList<ListNode> lists) {
        //既然是需要合并k个已经升序的链表，那么我们就可以利用一个堆，采用小根堆，根元素就是最小的元素
        //我们遍历链表，把表头头加到堆中，那么就会自动生成小根堆，每次弹出堆顶元素再拼接即可
        //注意我们把表头放进去，其实就是代表着这整个小的链表也放进去了，所以我们弹出堆顶元素的时候
        //第一次弹出的是头结点，然后如果头结点后面还有元素的话，还是需要把后面的节点加到堆中，然后这样就可以
        //保证一直弹出的都是最小的节点
        PriorityQueue<ListNode> pq = new PriorityQueue<ListNode>(new Comparator<ListNode>() {
            @Override
            public int compare(ListNode o1, ListNode o2) {
                return o1.val-o2.val;
            }
        });
        int len=lists.size();
        ListNode res=new ListNode(-1);
        ListNode cur=res;
        for(int i=0;i<len;i++){
            if(lists.get(i)!=null) {
                pq.add(lists.get(i));
            }
        }
        //合并链表
        while (!pq.isEmpty()){
            //弹出堆顶元素，其实代表整个小链表
            ListNode tmp=pq.poll();
            //不用比较元素大小，因为已经是最小的了，直接拼接
            cur.next=tmp;
            cur=cur.next;
            //弹出的节点后面还有节点，继续入队，保证下次弹出的是最小
            if(tmp.next!=null){
                pq.add(tmp.next);
            }
        }
        return res.next;
    }
}
